# 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
# 要求不能创建任何新的节点，只能调整树中节点指针的指向。

# 来源：力扣（LeetCode）
# https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
from collections import deque


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None
        queue = deque()

        def f(node, queue):
            if not node:
                return
            f(node.left, queue)
            queue.append(node)
            f(node.right, queue)

        f(root, queue)
        head = queue.popleft()
        pre = head
        while queue:
            cur = queue.popleft()
            cur.left = pre
            pre.right = cur
            pre = cur
        head.left = pre
        pre.right = head
        return head


class Solution1:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root:
            return None

        def recur(node):
            if not node:
                return
            recur(node.left)
            if self.pre:
                self.pre.right, node.left = node, self.pre
            else:
                self.head = node
            self.pre = node
            recur(node.right)

        self.pre = None
        recur(root)
        self.head.left, self.pre.right = self.pre, self.head

        return self.head

